package question.solution1011;

import question.SolutionTemplate;

import java.util.Arrays;

public class Solution1011 implements SolutionTemplate {

    public int shipWithinDays(int[] weights, int D) {
        int maxCarry = Arrays.stream(weights).sum();
        int minCarry = Math.max(Arrays.stream(weights).max().getAsInt(), maxCarry/weights.length);

        while(minCarry<maxCarry){
            int midCarry = (maxCarry+minCarry)/2;
            int needD = 1;
            int carryAll = 0;
            for(int i=0;i<weights.length;i++){
                if(carryAll+weights[i]>midCarry){
                    needD++;
                    carryAll=0;
                }
                carryAll+=weights[i];
            }
            if(needD>D){
                minCarry = midCarry+1;
            }else{
                maxCarry = midCarry;
            }
        }
        return minCarry;
    }

    @Override
    public void test() {
        int[] weights = {1,2,3,4,5,6,7,8,9,10};
        int D = 10;
        int result = shipWithinDays(weights, D);
        System.out.println();
    }

}
